package class04;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @description: 利用双链表实现双端队列
 * @time: 2021/7/17 18:58
 * @author: lhy
 */
public class DoubleLinkedListToDeque {
    public static class Node<V> {
        public V value;
        public Node<V> pre;
        public Node<V> next;

        public Node(V value) {
            this.value = value;
            this.pre = null;
            this.next = null;
        }
    }

    public static class MyDeque<V>{
        private Node<V> head;
        private Node<V> tail;
        private int size;

        public MyDeque(){
            this.head = null;
            this.tail = null;
            this.size = 0;
        }
        public boolean isEmpty(){
            return size == 0;
        }
        public int size(){
            return size;
        }
        public void addFirst(V value){
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            }else {
                cur.next = head;
                head.pre = cur;
                head = cur;
            }
            size++;
        }
        public void addLast(V value){
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            }else {
                tail.next = cur;
                cur.pre = tail;
                tail = cur;
            }
            size++;
        }

        public V pollFirst(){
            if (head == null){
                return null;
            }
            V ans = head.value;
            if (head == tail){
                head = null;
                tail = null;
            }else {
                head = head.next;
                head.pre = null;
            }
            size--;
            return ans;
        }

        public V pollLast(){
            if (head == null) {
                return null;
            }
            V ans = tail.value;
            if (head == tail){
                head = null;
                tail = null;
            }else {
                tail = tail.pre;
                tail.next = null;
            }
            size--;
            return ans;
        }

        public V peekFirst(){
            return head == null ? null : head.value;
        }
        public V peelLast(){
            return tail == null ? null : tail.value;
        }
    }

    public static void testDeque(int testTime, int maxValue){
        MyDeque<Integer> myDeque = new MyDeque<>();
        Deque<Integer> test = new LinkedList<>();
        System.out.println("MyDeque test begin...");
        for (int i = 0; i < testTime; i++) {
            if (myDeque.isEmpty() != test.isEmpty()) {
                System.out.println("myDeque.isEmpty() Oops!");
            }
            if (myDeque.size() != test.size()) {
                System.out.println("myDeque.size() Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                if (Math.random() < 0.5) {
                    myDeque.addFirst(num);
                    test.addFirst(num);
                } else {
                    myDeque.addLast(num);
                    test.addLast(num);
                }
            } else if (decide < 0.66) {
                if (!myDeque.isEmpty()) {
                    int num1,num2;
                    if (Math.random() < 0.5) {
                        num1 = myDeque.pollFirst();
                        num2 = test.pollFirst();
                    } else {
                        num1 = myDeque.pollLast();
                        num2 = test.pollLast();
                    }
                    if (num1 != num2) {
                        System.out.println("myDeque.poll() Oops!");
                    }
                }
            } else {
                if (!myDeque.isEmpty()) {
                    int num1,num2;
                    if (Math.random() < 0.5) {
                        num1 = myDeque.peekFirst();
                        num2 = test.peekFirst();
                    } else {
                        num1 = myDeque.peelLast();
                        num2 = test.peekLast();
                    }
                    if (num1 != num2) {
                        System.out.println("myDeque.peel() Oops!");
                    }
                }
            }
        }
        if (myDeque.size() != test.size()) {
            System.out.println("myDeque.size() Oops!");
        }
        while (!myDeque.isEmpty()) {
            int num1 = myDeque.pollFirst();
            int num2 = test.pollFirst();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("MyDeque test end!");
    }

    public static void main(String[] args) {
        int testTime = 5000000;
        int maxValue = 200000000;
        testDeque(testTime,maxValue);
    }
}
